package hpp.problems;

import hpp.structure.BinaryTreeNode;

import java.util.LinkedList;
import java.util.Queue;

/**
 * 写一个函数,输入一个二叉树,树中每个节点存放了一个整数值,函数返回这棵二叉树中相差最大的两个节点间的差值绝对值。请注意程序效率。
 * Created by hpp on 2017/8/31.
 */
public class Problem54 {

    public static void main(String[] args) {
        BinaryTreeNode root1=new BinaryTreeNode();
        BinaryTreeNode node1=new BinaryTreeNode();
        BinaryTreeNode node2=new BinaryTreeNode();
        BinaryTreeNode node3=new BinaryTreeNode();
        BinaryTreeNode node4=new BinaryTreeNode();
        BinaryTreeNode node5=new BinaryTreeNode();
        BinaryTreeNode node6=new BinaryTreeNode();
        root1.leftNode=node1;
        root1.rightNode=node2;
        node1.leftNode=node3;
        node1.rightNode=node4;
        node4.leftNode=node5;
        node4.rightNode=node6;
        root1.value=8;
        node1.value=8;
        node2.value=7;
        node3.value=9;
        node4.value=2;
        node5.value=4;
        node6.value=7;
        findMax(root1);

    }

    public static void findMax(BinaryTreeNode root){

        int max = root.value;
        int min = root.value;
        if(root == null )
            return;
        Queue<BinaryTreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty())
        {
            BinaryTreeNode pNode = queue.poll();
            if (pNode.value > max )
                max = pNode.value;
            if (pNode.value < min)
                min = pNode.value;
            if(pNode.leftNode != null)
                queue.offer(pNode.leftNode);
            if(pNode.rightNode != null)
                queue.offer(pNode.rightNode);
        }
        System.out.println("最大差值为："+max +" - "+min+" = "+(max - min));
    }

}
